// 此源代码的使用受BSD样式
// 许可证的约束，该许可证可以在许可证文件中找到。

package types

import "bytes"

// 术语表表示由union 
// t1表示的类型集∪ y2∪ ... 术语t1到tn的类型集的tn。
// 如果所有术语都不相交，则术语列表为正常形式。
// termlist操作不要求操作数为正常形式。
type termlist []*term

// allTermlist表示所有类型的集合。
// 它是正常形式的。
var allTermlist = termlist{new(term)}

// String精确打印术语列表（无需标准化）。
func (xl termlist) String() string {
	if len(xl) == 0 {
		return "∅"
	}
	var buf bytes.Buffer
	for i, x := range xl {
		if i > 0 {
			buf.WriteString(" ∪ ")
		}
		buf.WriteString(x.String())
	}
	return buf.String()
}

// isEmpty报告termlist xl是否表示类型的空集。
func (xl termlist) isEmpty() bool {
	// 如果有非零项，则整个列表不是空的。
	// 如果术语表是正常形式，则最多需要一次迭代。
	for _, x := range xl {
		if x != nil {
			return false
		}
	}
	return true
}

// isAll报告termlist xl是否代表所有类型的集合。
func (xl termlist) isAll() bool {
	// 如果有𝓤 学期结束时，整个名单是𝓤. 
	// 如果术语表是正常形式，则最多需要
	// 一次迭代。
	for _, x := range xl {
		if x != nil && x.typ == nil {
			return true
		}
	}
	return false
}

// norm返回xl的正常形式。
func (xl termlist) norm() termlist {
	// 二次算法，但现在已经足够好了。
	// TODO（gri）修复渐近性能
	used := make([]bool, len(xl))
	var rl termlist
	for i, xi := range xl {
		if xi == nil || used[i] {
			continue
		}
		for j := i + 1; j < len(xl); j++ {
			xj := xl[j]
			if xj == nil || used[j] {
				continue
			}
			if u1, u2 := xi.union(xj); u2 == nil {
				// 如果遇到𝓤 学期结束时，整个名单是𝓤. 提前退出。
				// （请注意，这不仅仅是一个优化；
				// /如果我们继续下去，我们可能会以失败告终𝓤 术语
				// 和其他术语，结果不会是正常形式的
				// 。）ABCFDG 
				if u1.typ == nil {
					return allTermlist
				}
				xi = u1
			}
		}
		rl = append(rl, xi)
	}
	return rl
}

func (xl termlist) union(yl termlist) termlist {
	return append(xl, yl...).norm()
}

// intersect返回交叉点xl∩ 伊尔。
func (xl termlist) intersect(yl termlist) termlist {
	if xl.isEmpty() || yl.isEmpty() {
		return nil
	}

	// 二次算法，但现在已经足够好了。
	// TODO（gri）修复渐近性能
	var rl termlist
	for _, x := range xl {
		for _, y := range yl {
			if r := x.intersect(y); r != nil {
				rl = append(rl, r)
			}
		}
	}
	return rl.norm()
}

// equal报告xl和yl是否代表同一类型集。
func (xl termlist) equal(yl termlist) bool {
	// TODO（gri）这应该更有效
	return xl.subsetOf(yl) && yl.subsetOf(xl)
}

// 包括报告是否∈ xl码。
func (xl termlist) includes(t Type) bool {
	for _, x := range xl {
		if x.includes(t) {
			return true
		}
	}
	return false
}

// 上级报告是否为y⊆ xl码。
func (xl termlist) supersetOf(y *term) bool {
	for _, x := range xl {
		if y.subsetOf(x) {
			return true
		}
	}
	return false
}

// 子部分报告xl⊆ 伊尔。
func (xl termlist) subsetOf(yl termlist) bool {
	if yl.isEmpty() {
		return xl.isEmpty()
	}

	// xl的每个项x必须是yl 
	for _, x := range xl {
		if !yl.supersetOf(x) {
			return false // x不是yl 
		}
	}
	return true
}
